import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution310 {

    public static void main(String args[]) {
        Solution310 s = new Solution310();
        System.out.println(s.findMinHeightTrees(4, new int[][]{{1, 2}, {1, 3}, {1, 0}}));
    }

    HashMap<Integer, List<Integer>> e;
    HashMap<Integer, HashMap<Integer, Integer>> mp;

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> res = new ArrayList<>();
        if(n == 1){
            res.add(0);
            return res;
        }
        int[] h = new int[n];
        e = new HashMap<>();
        mp = new HashMap<>();
        for (int[] edge : edges) {
            e.putIfAbsent(edge[0], new ArrayList<>());
            e.get(edge[0]).add(edge[1]);

            e.putIfAbsent(edge[1], new ArrayList<>());
            e.get(edge[1]).add(edge[0]);
        }
        int minv = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            h[i] = dfs(-1, i);
            minv = Math.min(minv, h[i]);
        }

        for (int i = 0; i < n; i++) {
            if (h[i] == minv) {
                res.add(i);
            }
        }
        return res;
    }

    public int dfs(int p, int c) {
        if (mp.containsKey(p) && mp.get(p).containsKey(c)) {
            return mp.get(p).get(c);
        }
        int maxv = 0;
        for (Integer child : e.get(c)) {
            if (child != p) {
                maxv = Math.max(maxv, dfs(c, child) + 1);
            }
        }
        mp.putIfAbsent(p, new HashMap<>());
        mp.get(p).put(c, maxv);
        return maxv;
    }

}
